import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NM {
    //算法题：求四数之和；
    //给定一个数组和一个目标值；
    //从数组中找到四个数满足四个数的加和等于目标值；
    //要求返回的结果不能有重复的结果；
    public static List<List<Integer>> fun(int[] array,int target){
        List<List<Integer>> ret=new ArrayList<>();
        int n= array.length;
        Arrays.sort(array);
        for(int i=0;i<n;){
            for(int j=i+1;j<n;){
                int left=j+1;
                int right=n-1;
                int aim=target-array[i]-array[j];
                while(left<right){
                    int sum=array[left]+array[right];
                    if(sum<aim){
                        left++;
                    } else if (sum>aim) {
                        right--;
                    }else{
                        ret.add(Arrays.asList(array[i],array[j],array[right--],array[left++]));
                        //开始：去重一：
                        while(left<right&&array[left]==array[left-1]){
                            left++;
                        }
                        while(left<right&&array[right]==array[right+1]){
                            right--;
                        }
                    }
                }
                //开始：去重二：
                j++;
                while(j<n&&array[j]==array[j-1]){
                    j++;
                }
            }
            //开始：去重三：
            i++;
            while(i<n&&array[i]==array[i-1]){
                i++;
            }
        }
        return ret;
    }
    public static void main(String[] args){
        int[] array={1,0,-1,0,-2,2};
        List<List<Integer>> ret=fun(array,0);
        System.out.println(Arrays.asList(ret));
    }
}
